
#include "iostream"
#include "vector"
#include "unordered_map"
#include "unordered_set"
#include "algorithm"
#include "string"
#include "list"
#include "string.h"

struct Rule{
    int a;
    int b;
    Rule(int a,int b):a(a),b(b){

    }
};
class OneLoop{
public:
    std::vector<Rule> rules;
    std::unordered_map<int,bool> res;
    void rule_on_num(Rule r,int& i){
        int new_i=0;
        int ws=1;
        int i_cpy=i;
        while(i_cpy){
            int dqw=i_cpy%10;
//            new_i*=10;
            if(dqw==r.a){
                new_i+=ws*r.b;
//                new_i+=r.b;
            }else{
                new_i+=ws*dqw;
//                new_i+=dqw;
            }
            ws*=10;
            i_cpy/=10;
        }
        i=new_i;
    }
    void recur(int cnt,int num){
        if(res.find(num)!=res.end()){
//            已经有过
            return;
        }
        res[num]=1;

        for(int i=0;i<rules.size();i++){
//            if(rule_able(i))
            {
//                rule_stack.push_back(i);
                int num1=num;
                rule_on_num(rules[i],num1);
                recur(cnt+1,num1);
//                rule_stack.pop_back();
            }
        }
    }
    void run(
            int a,int b
            ){
        for(int i=0;i<b;i++){
            int c,d;std::cin>>c>>d;
            //记录规则
            rules.push_back(Rule(c,d));

        }
        recur(0,a);
        for(auto j:res){
            printf("%d ",j.first);
        }
    }
};
class Solution {
public:
    void run() {

        bool first = true;
        int a,b,c,d,e;
//        std::string s1,s2;
        while (
                std::cin>>a>>b
//                std::getline(std::cin,s1)
                )
        {
//            std::getline(std::cin,s2);
            OneLoop loop;
            loop.run(a,b);
        }
    }
};

int main() {
//    bool cur_num= true;
    Solution().run();
    return 0;
}

